from __future__ import print_function;

import os;
import io;
import sys;
import math;
import time;
import socket;
import ctypes;
import threading;
from json import loads;
from json import dumps;

try:
	import msvcrt;
except:
	import tty;
	import termios;

XG_OK = 1;
XG_FAIL = 0;
XG_ERROR = -1;
XG_IOERR = -2;
XG_SYSERR = -3;
XG_NETERR = -4;
XG_TIMEOUT = -5;
XG_DATAERR = -6;
XG_SYSBUSY = -7;
XG_PARAMERR = -8;
XG_NOTFOUND = -9;
XG_NETCLOSE = -10;
XG_NETDELAY = -11;
XG_SENDFAIL = -12;
XG_RECVFAIL = -13;
XG_AUTHFAIL = -14;
XG_DAYLIMIT = -15;
XG_DUPLICATE = -16;
XG_UNINSTALL = -17;
XG_DETCHCONN = -999999;

__win_cmd_hande__ = None;

class lock:
	def __init__(self):
		self._lock = threading.Lock();
	def begin(self):
		self._lock.acquire();
	def end(self):
		self._lock.release();

class stack:
	def __init__(self):
		self._data = [];
	def pop(self):
		val = self.size();
		if val <= 0: return None;
		val = self._data[val - 1];
		self._data.pop();
		return val;
	def push(self, val):
		self._data.append(val);
	def data(self):
		return tuple(self._data);
	def size(self):
		return len(self._data);
	def empty(self):
		return self.size() <= 0;
	def clear(self):
		self._data = [];

class queue(stack):
	def push(self, val):
		self._data.insert(0, val)

class fromdict:
	def __init__(self, data):
		for a, b in data.items():
			if isinstance(b, (list, tuple)): setattr(self, a, [obj(x) if isinstance(x, dict) else x for x in b]);
			else: setattr(self, a, obj(b) if isinstance(b, dict) else b);

class thread(threading.Thread):
	def __init__(self, func = None, args = None):
		threading.Thread.__init__(self);
		self._func = func;
		self._args = args;
	def run(self):
		sz = self._func.func_code.co_argcount;
		ps = self._args;
		if sz == 0: self._func();
		elif sz == 1: self._func(ps);
		elif sz == 2: self._func(ps[0], ps[1]);
		elif sz == 3: self._func(ps[0], ps[1], ps[2]);
		elif sz == 4: self._func(ps[0], ps[1], ps[2], ps[3]);
		elif sz == 5: self._func(ps[0], ps[1], ps[2], ps[3], ps[4]);
		elif sz == 6: self._func(ps[0], ps[1], ps[2], ps[3], ps[4], ps[5]);
		elif sz == 7: self._func(ps[0], ps[1], ps[2], ps[3], ps[4], ps[5], ps[6]);
		elif sz == 8: self._func(ps[0], ps[1], ps[2], ps[3], ps[4], ps[5], ps[6], ps[7]);

class CommException(Exception):
	def __init__(self, code, msg = None):
		self.errcode = code;
		if msg:
			self.errmsg = msg;
		else:
			self.errmsg = error(code);
	def __str__(self):
		return self.errmsg;
	def getErrorCode(self):
		return self.errcode;
	def getErrorString(self):
		return self.errmsg;

def gets():
	return input();

def getch():
	if IsLinuxSystem():
		fd = sys.stdin.fileno();
		settings = termios.tcgetattr(fd);
		tty.setraw(fd);
		ch = sys.stdin.read(1).decode();
		termios.tcsetattr(fd, termios.TCSADRAIN, settings);
	else:
		import msvcrt;
		ch = msvcrt.getch().decode();
	return ch;

def getip():
	if IsLinuxSystem(): return os.popen("ifconfig | grep 'inet' | grep -v '127.0.0.1' | cut -d: -f2 | awk '{print $2}' | head -1").read().strip();
	else: return socket.gethostbyname(socket.gethostname());

def puts(msg):
	print(msg);

def atoi(str):
	pos = 0;
	if str[0] == '+' or str[0] == '-':
		pos = 1;
	while pos < len(str):
		if str[pos] >= '0' and str[pos] <= '9': pos = pos + 1;
		else: break;
	return int(str[0:pos]);

def atof(str):
	pos = 0;
	dot = 0;
	if str[0] == '+' or str[0] == '-':
		pos = 1;
	while pos < len(str):
		if (str[pos] >= '0' and str[pos] <= '9'):
			pos = pos + 1;
		elif str[pos] == '.' and dot == 0:
			pos = pos + 1;
			dot = 1;
		else: break;
	return float(str[0:pos]);

def sleep(sec):
	time.sleep(sec);

def error(code):
	if code == XG_FAIL: return 'process failed';
	if code == XG_SYSBUSY: return 'system busy';
	if code == XG_DATAERR: return 'invalid data';
	if code == XG_TIMEOUT: return 'resource timeout';
	if code == XG_PARAMERR: return 'parameter error';
	if code == XG_AUTHFAIL: return 'permission denied';
	if code == XG_NOTFOUND: return 'resource not found';
	if code == XG_DUPLICATE: return 'resource duplicate';
	return 'system error';

def printf(msg):
	print(msg, end='');
	sys.stdout.flush();

def start(func, args = None):
	runner = thread(func, args);
	runner.start();
	return runner;

def json(obj, charset = 'unicode_escape'):
	return dumps(obj).encode().decode(charset);

def parse(msg, charset = 'unicode_escape'):
	if isinstance(msg, bytes): return loads(msg.decode(charset));
	else: return loads(msg);

def IsLinuxSystem():
	global __win_cmd_hande__;
	if __win_cmd_hande__ == None and hasattr(ctypes, 'windll'):
		__win_cmd_hande__ = ctypes.windll.kernel32.GetStdHandle(-11);
	if __win_cmd_hande__: return False;
	else: return True;

def ClearConsole():
	if IsLinuxSystem(): os.system('clear');
	else: os.system('cls');

def RunCommand(cmd):
	fd = os.popen(cmd, 'r', -1);
	if fd == None: return None;
	data = fd.read();
	fd.close();
	return data;

def CheckCommand(msg):
	printf(msg);
	while True:
		n = getch();
		if n == 'Y' or n == 'y':
			SetTextColor('GREEN');
			printf(' (YES)\n');
			SetTextColor('WHITE');
			return True;
		if n == 'N' or n == 'n':
			SetTextColor('RED');
			printf(' (NO)\n');
			SetTextColor('WHITE');
			return False;
	return False;

def GetFileList(path):
	res = [];
	for val in os.listdir(path):
		if os.path.isfile(os.path.join(path, val)): res.append(val);
	return res;

def GetFolderList(path):
	res = [];
	for val in os.listdir(path):
		if os.path.isdir(os.path.join(path, val)): res.append(val);
	return res;

def SetTextColor(color):
	key = color.lower();
	if IsLinuxSystem():
		colorlist = {'red': 31, 'green': 32, 'blue': 34, 'yellow': 33, 'white': 37};
		if colorlist.has_key(key): printf('\033[%dm' % (colorlist[key]));
	else:
		colorlist = {'red': 4, 'green': 2, 'blue': 1, 'yellow': 6, 'white': 7};
		if colorlist.has_key(key): ctypes.windll.kernel32.SetConsoleTextAttribute(__win_cmd_hande__, colorlist[key]);

def Throw(code, msg = None):
	raise CommException(code, msg);

def SystemPause(msg = None):
	if msg == None: msg = '\npress any key to continue';
	if len(msg) > 0: print(msg);
	sys.stdout.flush();
	getch();

def GetDateTime(sec = None):
	if sec == None: sec = time.time();
	sec = time.localtime(sec);
	return fromdict({'year': sec.tm_year, 'mon': sec.tm_mon, 'day': sec.tm_mday, 'hour': sec.tm_hour, 'min': sec.tm_min, 'sec': sec.tm_sec, 'wday': sec.tm_wday + 1, 'yday': sec.tm_yday});

def GetDateTimeString(sec = None):
	if sec == None: sec = time.time();
	sec = time.localtime(sec);
	return '%04d-%02d-%02d %02d:%02d:%02d' % (sec.tm_year, sec.tm_mon, sec.tm_mday, sec.tm_hour, sec.tm_min, sec.tm_sec);

def SelectCommand(menus, msg = None):
	i = 0;
	ch = 0;
	if msg and len(msg) > 0:
		puts(msg);
		puts('-----------------------------------------');
	for item in menus:
		i = i + 1;
		puts(' %d.%s' % (i, item));
	puts('------------------------------------------');
	printf(' press numeric key to select the menu : ');
	while True:
		ch = getch();
		ch = ord(ch) - ord('0');
		if ch >= 1 and ch <= len(menus):
			puts('%d' % ch);
			return ch;
	return 0;

def PrintHexData(data, sz = None):
	i = 0;
	n = 0;
	buffer = '';
	if sz == None or sz <= 0: sz = len(data);
	while i < sz:
		if i % 16 == 0:
			if n == 16:
				n = 0;
				SetTextColor('GREEN');
				printf(" %s" % buffer);
				SetTextColor('WHITE');
				buffer = '';
			SetTextColor('YELLOW');
			printf("[%04X] " % i);
			SetTextColor('WHITE');
		val = ord(data[i]);
		printf('%02X ' % (val % 256));
		if val > 0X1F and val < 0X7F: buffer = buffer + data[i];
		else: buffer = buffer + '.';
		n = n + 1;
		i = i + 1;
	if n > 0:
		j = n;
		while j < 16:
			printf("   ");
			j = j + 1;
	SetTextColor('GREEN');
	printf(' %s\n' % buffer);
	SetTextColor('WHITE');

def LoadConfig(path, charset = 'UTF-8'):
	cfg = {};
	file = open(path, 'rb');
	for line in file:
		line = line.decode(charset).strip(' \r\n\t');
		if len(line) > 2 and line[0:1] != '-' and line[0:1] != '#':
			pos = line.find('=');
			if pos > 0:
				key = line[0:pos].strip(' \r\n\t');
				val = line[pos+1:].strip(' \r\n\t');
				if val[0:1] == "'" and val[-1:] == "'": val = val[1:-1];
				elif val[0:1] == "\"" and val[-1:] == "\"": val = val[1:-1];
				if val.isnumeric():
					val = int(val);
				elif not IsLinuxSystem():
					tmp = '';
					vec = val.split('/');
					for item in vec:
						tmp = tmp + '/';
						pos = item.find('$');
						if pos < 0: tmp = tmp + item;
						else: tmp = tmp + item[0:pos] + '%' + item[pos+1:].strip('{()}') + '%';
					val = tmp[1:];
				cfg[key] = val;
	file.close();
	return cfg;

def CheckLength(msg, maxlen, required = True):
	if msg == None: return not required;
	minlen = 1;
	sz = len(msg);
	if (isinstance(maxlen, list) or isinstance(maxlen, tuple)) and len(maxlen) > 1:
		minlen = maxlen[0];
		maxlen = maxlen[1];
	if required: return sz >= minlen and sz <= maxlen;
	else: return sz == 0 or (sz >= minlen and sz <= maxlen);

def ReadPassword(cnt = 32, echo = '*', func = None):
	i = 0;
	ch = 0;
	str = '';
	while i < cnt:
		ch = getch();
		if ch == 0 or ch == '\n' or ch == '\r': break;
		if ch == '\b':
			if i == 0: continue;
			i = i - 1;
			if len(echo) > 0: printf('\b \b');
		else:
			if func == None:
				if len(echo) > 0: printf('*');
				str = str + ch;
			elif func(ch):
				if len(echo) > 0: printf(echo);
				str = str + ch;
			i = i + 1;
	return str;

def GetCompletedString(str, sz, left = False, ch = ' '):
	cnt = sz - len(str);
	if cnt <= 0: return str[0:sz];
	if left:
		while cnt > 0:
			str = ch + str;
			cnt = cnt - 1;
	else:
		while cnt > 0:
			str = str + ch;
			cnt = cnt - 1;
	return str;